package leecode.二叉树;

/**
 * @author wangxi created on 2021/6/7 23:58
 * @version v1.0
 *
 * https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/
 *
 * 给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
 *
 * 注意：leetcode上这个题，当数组元素个数是偶数时，没有严格要求中间节点取
 * (left + right)/2 还是 (left + right + 1)/2
 *
 * 但是在nowcoder上同样的题，要求数组元素个数是偶数时，mid取后面一个元素
 */
public class SortedArrayToBST {




    public TreeNode sortedArrayToBST(int[] num) {
        // write code here
        if (num == null || num.length <= 0) {
            return null;
        }
        return help(num, 0, num.length - 1);
    }

    private TreeNode help(int[] num, int left, int right) {
        if (left > right) {
            return null;
        }

        // 如果要求 mid取后面一个元素. 注意下面写法的技巧性
//        int mid = (left + right + 1)/2;

        int mid = left + (right - left)/2;
        TreeNode root = new TreeNode(num[mid]);
        // mid节点使用后，不能再参与找寻中间节点的数组中，否则只有一个元素时，递归是无法退出的。
        root.left = help(num, left, mid - 1);
        root.right = help(num, mid + 1, right);
        return root;
    }
}
